173B - Chamber of Secrets - CodeForces Solution

//#pragma GCC optimize("O3")
#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define ld long double
#define f first
#define s second
#define show(x) cout << (#x) << " is " << (x) << endl
#define forn(i, n) for (int i = 0; i < int(n); i++)
#define sz(v) ((ll)((v).size()))
#define posmod(v, m) ((v) % (m) + (m)) % m;
#define fast ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
using namespace std;
template <typename T>
ostream& operator <<(ostream& out, const vector<T>& v){forn(i,sz(v)) out<<v[i]<<' ';return out;}
const int N = 1000 + 5;
const ll mod = 1e9 + 7;
int dx[] = {-1, +1, +0, +0, +1, +1, -1, -1};
int dy[] = {+0, +0, +1, -1, +1, -1, +1, -1};

char a[N][N];
bool vis[N][N];
int n, m;

bool valid(int x, int y){
    return x >= 0 && x < n && y >= 0 && y < m;
}

void test()
{
    cin >> n >> m;
    for(int i = 0; i < n; i++)
        for(int j = 0; j < m; j++)
            cin >> a[i][j];
    queue<pair<int, int>> q;
    for(int i = 0; i < m; i++){
        if (a[n - 1][i] == '#'){
            vis[n - 1][i] = true;
            q.emplace(n - 1, i);
        }
    }
    int dep = 1;
    while(!q.empty()){
        int sz = q.size();
        while(sz--){
            auto cur = q.front(); q.pop();
            for(int i = 0; i < 4; i++){
                int x = cur.f, y = cur.s;
                while(valid(x + dx[i], y + dy[i]) && !vis[x + dx[i]][y + dy[i]]){
                    x += dx[i], y += dy[i];
                    if (a[x][y] == '#'){
                        if (x == 0)
                            return void(cout << dep + 1);
                        vis[x][y] = true;
                        q.emplace(x, y);
                    }
                }
            }
        }
        dep++;
    }
    cout << -1;
}

int main() {
    fast
    int t = 1;
//    cin >> t;

    while(t--){
        test();
    }
}